
def insert_sort(alist):

    """
        插入排序：认为第一个元素是最小的，从第二个依次取出去放到前面合适的位置，如果比第一个小，就插到第一个前面，再去取第三个元素比较
        和选择排序不同，选择排序是遍历一遍寻找最小的，放在前面，再比较剩下最小的，放在第二个位置
    """

    for j in range(1, len(alist)):
        """
            j 表示拿第二个元素到最后一个元素去跟前一个去比较的循环
            最优时间复杂度O(n)，进去就break的情况
            最坏时间复杂度O(n^2)
        """
        i = j

        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                # 表示当前元素所移动的位置前面正好合适，结束当前元素的移动
                break
